package Leetcode.Stack;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @Author: kirito
 * @Date: 2024/4/16 12:23
 * @Description:
 *  好子数组的最大分数
 * 已解答
 * 困难
 * 相关标签
 * 相关企业
 * 提示
 * 给你一个整数数组 nums （下标从 0 开始）和一个整数 k 。
 *
 * 一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1) 。一个 好 子数组的两个端点下标需要满足 i <= k <= j 。
 *
 * 请你返回 好 子数组的最大可能 分数 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,4,3,7,4,5], k = 3
 * 输出：15
 * 解释：最优子数组的左右端点下标是 (1, 5) ，分数为 min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15 。
 * 示例 2：
 *
 * 输入：nums = [5,5,4,5,4,1,1,1], k = 0
 * 输出：20
 * 解释：最优子数组的左右端点下标是 (0, 4) ，分数为 min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20 。
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 105
 * 1 <= nums[i] <= 2 * 104
 * 0 <= k < nums.length
 */

public class maximumScore {
    public static void main(String[] args) {

    }
    //以min为中心点一直遍历  思路很巧妙
    public static int maximumScore(int[] nums, int k) {
        // 定义变量
        int n = nums.length; // 数组的长度
        int left = k - 1; // 初始化左边界，从k-1开始
        int right = k + 1; // 初始化右边界，从k+1开始
        int ans = 0; // 用于存储最终的分数

        // 使用循环来找到最大的元素，并且其连续出现次数最大
        for (int min = nums[k];; --min) {
            // 向左移动直到找到一个小于当前元素的数
            while (left >= 0 && nums[left] >= min) {
                --left;
            }
            // 向右移动直到找到一个小于当前元素的数
            while (right < n && nums[right] >= min) {
                ++right;
            }
            // 计算以i为最大元素的连续子数组的分数
            // 分数等于(right - left - 1) * i
            // 其中right - left - 1是连续元素i的个数
            ans = Math.max(ans, (right - left - 1) * min);
            // 如果左边界left已经到达-1，右边界right已经到达数组的末尾n，那么结束循环
            if (left == -1 && right == n) {
                break;
            }
        }
        // 返回最终的分数
        return ans;
    }


    /**
     * 题意得  子数组尽可能长且里面的最小值要尽可能大
     * 1.暴力法遍历
     * 2.单调栈   思路展示不这么清晰
     * 3.双指针    思路巧妙  值得学习
     * @param nums
     * @param k
     * @return
     */
    public static int maximumScore2(int[] nums, int k) {
        // 定义变量
        int n = nums.length; // 数组的长度
        int[] left = new int[n]; // 存储每个元素左边第一个比它小的元素的索引
        Deque<Integer> st = new ArrayDeque<>(); // 辅助栈，用于维护 left 数组

        // 从左到右遍历数组，填充 left 数组
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            // 弹出栈中所有大于等于 x 的元素
            while (!st.isEmpty() && x <= nums[st.peek()]) {
                st.pop();
            }
            // left[i] 存储的是 x 左边第一个比它小的元素的索引
            // 如果栈为空，说明 x 没有比它小的元素，则 left[i] 设为 -1
            // 否则，left[i] 设为栈顶元素的索引
            left[i] = st.isEmpty() ? -1 : st.peek();
            // 将 i 压入栈中
            st.push(i);
        }

        int[] right = new int[n]; // 存储每个元素右边第一个比它小的元素的索引
        st.clear(); // 清空辅助栈
        for (int i = n - 1; i >= 0; i--) {
            int x = nums[i];
            // 弹出栈中所有大于等于 x 的元素
            while (!st.isEmpty() && x <= nums[st.peek()]) {
                st.pop();
            }
            // right[i] 存储的是 x 右边第一个比它小的元素的索引
            // 如果栈为空，说明 x 没有比它小的元素，则 right[i] 设为 n（数组末尾）
            // 否则，right[i] 设为栈顶元素的索引
            right[i] = st.isEmpty() ? n : st.peek();
            // 将 i 压入栈中
            st.push(i);
        }

        int ans = 0; // 用于存储最终的分数

        // 遍历数组，计算每个元素为最大元素的连续子数组的分数
        for (int i = 0; i < n; i++) {
            int h = nums[i];
            int l = left[i];
            int r = right[i];
            // 只有当 l < k 且 k < r 时，才计算分数
            // 这意味着 k 处于 l 和 r 之间，形成一个连续子数组
            if (l < k && k < r) {
                // 分数等于 h * (r - l - 1)
                // 其中 r - l - 1 是连续元素 h 的个数
                ans = Math.max(ans, h * (r - l - 1));
            }
        }

        // 返回最终的分数
        return ans;
    }

}
